⟸ Go Back ⟸
Exercise 1 (Homework 3).
(pumping lemma, dyck language)

Variations on a^n b^n

We saw in class that A=\{a^nb^n \mid n\in \mathbb N\} is not a regular language.

  1. Consider now a language L\subseteq A. Show that L is regular if and only if L is finite.

    Before proving the general result it might be easier to prove the special cases to get ideas on how to proceed in general.

    • How would you show that \{a^nb^n \mid n\in 2\mathbb N\} is not regular?
    • How would you show it with \{a^nb^n \mid n\in 3\mathbb N\}?

  2. Show that the following languages are not regular.

    1. \{a^nb^m \mid n,m\in \mathbb N\land n\leq m\}
    2. \{a^nb^m \mid n,m\in \mathbb N\land n\geq m\}
    3. \{a^nb^m \mid n,m\in \mathbb N\land n\neq m\}
    4. \{a^{2n}b^n \mid n\in 2\mathbb N\}

    Using the pumping lemma directly is doable but a bit tricky. It is simpler to use first closure properties of regular languages.

  3. Show that the following languages over \{a,b,c\} are not regular.

    1. \{c^ma^nb^n \mid n,m\in \mathbb N\}
    2. \{a^nc^mb^n \mid n,m\in \mathbb N\}
    3. \{a^nb^nc^m \mid n,m\in \mathbb N\}
    4. \{a,b\}^* \cup \{c^ma^nb^n \mid n,m\in \mathbb N\}

  4. Show that the Dyck language is not regular, that is the language of all well-balanced parentheses is not regular. More precisely, given the alphabet \Sigma=\{(,)\}, show that the language \{w\in \Sigma^* \mid |w|_(=|w|_) \land \text{for every prefix $u$ of $w$} \ \ |u|_(\geq |u|_)\}

    is not regular.